#include "types.h"
#include "page.h"
#include "panic.h"
#include "multiboot.h"

unsigned kernelpde[1024] __attribute__((aligned(4096)));
//unsigned kernelpte[1024] __attribute__((aligned(4096)));

unsigned char pdebm[32];	/* 4M*32*8 1GB kernel space */
unsigned char ptebm[32*1024];	/* 32*1024*4K*8 1G */

uint32 MEMTOP = 0;


#define KERN_BASE 0xC0000000
#define KERN_TOP 0xE0000000 	/* 512 MB */
#define MAXPHYMEM (KERN_TOP - KERN_BASE)
#define LOW_MEM_BOUND (0x100000)

#define PAGE_SIZE 4096
#define PG_BCKT_NUM 10
extern void newgdt(); 		/* main.s */

struct page_node {
     struct page_node* prev;
     struct page_node* next;
     uint32 length;
     uint32 blank[1021];
};

struct page_node *page_root_node = NULL;

struct bucket {
     uint16 size; 		/* 2^order */
     uint16 number;		/* number of items in bucket */
     uint32* next;
} pg_bucket[PG_BCKT_NUM];

void pg_bucket_init(uint32 start, uint32 end)
{
     page_root_node = (struct page_node*) start;
     page_root_node->length = (end - start) / 4096;
     page_root_node->next = NULL;
}


struct page_node*
__page_linked_list_delete(struct page_node** head, struct page_node* node)
{
     /* if node is head */
     struct page_node *prev = node->prev,
	  *next = node->next;
     
     if (prev == NULL)
     {
	  *head = next;
	  (*head)->prev = NULL;
     }
     else
     {
	  node->prev->next = node->next;
	  if (node->next != NULL) /* make sure node is not tail */
	  {
	       node->next->prev = node->prev;
	  }
     }
	  
     return node;
}

void __page_linked_list_insert(struct page_node** head, struct page_node* node)
{
     /* if node is head */
     if (node < *head)
     {
	  node->next = *head;
	  node->prev = NULL;	  
	  (*head)->prev = node;
	  *head = node;

	  return;
     }

     /* find the proper node and insert after it */
     struct page_node* iter = *head;
     for (;iter->next != NULL; iter = iter->next)
     {
	  if (node > iter && node < iter->next)
	  {
	       break;
	  }
     }

     /* ok, found it, note iter may be the *tail* */
     node->next = iter->next;
     node->prev = iter;
     if (iter->next != NULL)
     {
	  iter->next->prev = node;
     }
     iter->next = node;
}

/* merge adjacent nodes if possible */
void __page_linked_list_adjacent_merge(struct page_node* node)
{
     struct page_node *prev = node->prev,
	  *next = node->next;
     
     /* merge left */
     if (prev != NULL)
     {
	  if ((uint32)prev + prev->length*PAGE_SIZE == (uint32)node)
	  {
	       prev->length += node->length;
	       prev->next = next;
	       node = prev;
	  }
     }
     /* merge right */

     if (next != NULL)
     {
	  if ((uint32)(node) + node->length*PAGE_SIZE == (uint32)(next))
	  {
	       node->length += next->length;
	       node->next = next->next;
	  }
     }
}

/* alloc num of pages in linked list
   algorithm is first fit
 */
void*  __page_linked_list_alloc(int num)
{
     struct page_node* node;

     /* walk through the linkded list  */
     for (node = page_root_node; node != NULL; node = node->next)
     {
	  if (node->length >= num)
	  {
	       break;		/* we found one!!! */
	  }
	  
     }

     if (node == NULL)
	  panic("page allocation failed\n");   /* TODO: not enough memory, PANIC */

     /* If we got more than required, divide into 2 nodes */
     if (node->length > num)
     {
	  struct page_node* tmp = (struct page_node*)(node + num);
	  tmp->prev = node;
	  tmp->next = node->next;
	  tmp->length = node->length - num;
	  node->next = tmp;
	  if (tmp->next != NULL)
	  {
	       tmp->next->prev = tmp;
	  }
     }

     return __page_linked_list_delete(&page_root_node, node);
}

/* free num of pages to the linked list
   adjacent nodes will be merged
 */
void __page_linked_list_free(void* addr, int num)
{
     struct page_node* node = (struct page_node*) addr;
     
     node->length = num;
     __page_linked_list_insert(&page_root_node, node);
     __page_linked_list_adjacent_merge(node);
}

void __page_linked_list_dump()
{
     struct page_node* iter = page_root_node;
     while (iter != NULL)
     {
	  printk("|0x%x:%d|->", iter, iter->length);
	  iter = iter->next;
     }

     printk("NULL\n");
}

/* init linked list head node
 *
 * @param start: start address of the heap
 */
void page_linked_list_init(void* start)
{
     page_root_node = (struct page_node*) start;

     page_root_node->prev = NULL;
     page_root_node->next = NULL;
     page_root_node->length = (MEMTOP - (uint32)start)/PAGE_SIZE;
}

void mem_probe(multiboot_info_t* mbi)
{
     /* convert to linear address by adding kernel addr offset
	note: every pointer saved before should do the work
      */

     multiboot_info_t* mbt = (multiboot_info_t*) ((uint32)mbi + 0xC0000000);
     printk("  flags: 0x%x   !! \n", &mbi);
     if (CHECK_FLAG(mbt->flags, 6))
     {
	  multiboot_memory_map_t *mmap;
     
	  printk ("mmap_addr = 0x%x, mmap_length = 0x%x\n",
	  	  (unsigned) mbt->mmap_addr, (unsigned) mbt->mmap_length);
	  for (mmap = (multiboot_memory_map_t *) (0xC0000000 | mbt->mmap_addr);
	       (unsigned long) mmap < mbt->mmap_addr + 0xC0000000 + mbt->mmap_length;
	       mmap = (multiboot_memory_map_t *) ((unsigned long) mmap
						  + mmap->size + sizeof (mmap->size)))
	  {
	       /* printk ("size = %x, base_addr = 0x%x," */
	       /* 	       " length = 0x%x, type = 0x%x\n", */
	       /* 	       mmap->size, */
	       /* 	       /\* (uint32)(mmap->addr >> 32), *\/ */
	       /* 	       (uint32)(mmap->addr & 0xffffffff), /\*  *\/ */
	       /* 	       /\* (uint32)(mmap->len >> 32), *\/ */
	       /* 	       (uint32)(mmap->len & 0xffffffff), */
	       /* 	       mmap->type); */
	       if (mmap->addr == LOW_MEM_BOUND) /* we only make use of the first area in upper_mem */
	       {
		    MEMTOP = (mmap->len + LOW_MEM_BOUND > MAXPHYMEM) ? MAXPHYMEM : (LOW_MEM_BOUND + mmap->len);
	       }
	  }
     }     
}

extern uint32 end; 		/* kernel end */
void init_paging(multiboot_info_t* mbt)
{
     mem_probe(mbt);
     printk("memory probed, MEMTOP:0x%x\n", MEMTOP);

     uint32 pte_number = MEMTOP/PAGE_SIZE;
     uint32 pte_page_number = MEMTOP/(4*1024*1024) + 1; /* map physcial memory */
     uint32* pte_pointer = &end;

     
     int i;
     for (i = 0; i < pte_number; ++i)
     {
	  pte_pointer[i] = i * 4096 | PAGE_P | PAGE_RW;
     }

     for (i = 0; i < pte_page_number; ++i)
     {
	  kernelpde[768 + i] =  ((((uint32)pte_pointer - KERN_BASE) + 4*1024*i)|PAGE_P);
     }

     /* now we maped all physcial memory to kernel address space
	note we used first pte_page_number pages after kernel end
	to maitain the structure

	so heap will start at &end + pte_page_number*PAGE_SIZE
      */
//     kernelpde[768] = (unsigned)(((unsigned)kernelpte - 0xC0000000) | 0x3);
     pte_pointer[0] &= ~PAGE_P;
     kernelpde[0] = (((uint32)pte_pointer - KERN_BASE) | PAGE_P);

     unsigned cr3 = (unsigned) ((unsigned)kernelpde - 0xC0000000);

     asm volatile("mov %0, %%cr3;"
		  "mov %%cr0, %%eax;"
		  "or $0x80000000, %%eax;"
		  "mov %%eax, %%cr0"::"r"(cr3):"eax");
     newgdt();
     
     

}

void mm_init(multiboot_info_t* mbi)
{
     init_paging(mbi);

     uint32 page_table_size = (MEMTOP/(4*1024*1024) + 1) * PAGE_SIZE;

     page_linked_list_init(page_table_size + &end);

     printk("root node 0x%x\n", page_root_node);
     __page_linked_list_dump();
     void* ptr1 =  __page_linked_list_alloc(1);
     __page_linked_list_dump();     
     void* ptr2 =  __page_linked_list_alloc(8);
     __page_linked_list_dump();     
     void* ptr3 =  __page_linked_list_alloc(4);
     __page_linked_list_dump();     
     printk("test alloc: 0x%x\t 0x%x\t 0x%x\n", ptr1, ptr2, ptr3);

     __page_linked_list_free(ptr2, 8);
     __page_linked_list_dump();
     ptr2 = __page_linked_list_alloc(4);
     printk("test free ptr2,8 alloc: 0x%x\n", ptr2);

     __page_linked_list_dump();
     __page_linked_list_free(ptr1, 1);
     __page_linked_list_dump();
     __page_linked_list_free(ptr2, 4);
     __page_linked_list_dump();
     __page_linked_list_free(ptr3, 4);
     __page_linked_list_dump();
     
     printk("all done: 0x%x, size:%d\n", page_root_node, page_root_node->length);
     
}
     
/* pdebm bitmaps a whole page dir which indcates
 * if there is free page entry in a page dir.
 *
 * ptebm bitmaps a page table

 */

int get_bit_num(unsigned char bit, int val)
{
     int i = 0;
     for (i = 0; i < 8; i++)
     {
	  if (((bit >> i) & 1) == 0)
	  {
	       return i;
	  }
     }
     return -1;
}

int get_page_num()
{
     int pg_dir = 0;
     for(; pg_dir < 32; pg_dir++)
     {
	  if(pdebm[pg_dir] != 0xFFFFFFFF)
	  {
	       break;
	  }
     }

     /* TODO: panic */
     if (pg_dir == 32)
     {
	  return -1;
     }


     unsigned *pg_tbl = (unsigned*)(ptebm + pg_dir * 1024);

     int i;
     for(i = 0; i < 1024; ++i)
     {
	  if (pg_tbl[i] != 0xFFFFFFFF)
	  {
	       break;
	  }
     }

     if (i == 1024) 		/* no free page, change pdebm */
     {
	  pdebm[pg_dir] = 0xFFFFFFFF;
	  /* TODO: search next hole */
     }
     else
     {
	  unsigned char bitmap = pg_tbl[i];
	  int tmp = get_bit_num(bitmap, 0);

	  return ((unsigned)pg_tbl - (unsigned)ptebm)*8 + tmp;
     }

     return 0;
}	  

void* alloc_pages(uint32 size)
{
     assert(size % PAGE_SIZE == 0);     
     return __page_linked_list_alloc(PAGE_SIZE / size);
}

void free_s_pages(void* addr, uint32 size)
{
     assert(size % PAGE_SIZE == 0);
     return __page_linked_list_free(addr, size / PAGE_SIZE);
}

